package com.fw.structure.recursion;

/**
 * 回溯算法 - 八皇后问题 解法
 *   8 x 8 棋盘中，每一个皇后摆放的位置 不能在同一行，同一列，同一斜线。
 */
public class EightQueens {

    private int max = 8; // 八个皇后

    private int[]  array = new int[max]; // 摆放不同的棋盘
    static int count = 0;

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.check(0);
        System.err.println(count);
    }

    /**
     * 开始解法
     * @param n
     */
    private void check(int n){
        // 如果 n == 8 说明 是第9个皇后，不在进行摆放！
        if (n == max){
            print();
            return;
        }

        /**
         * 对这段for 循环 递归代码的解释
         *
         * 1. 假设第 n = 0 进入 for 循环，那么第一行 第一列 已经被占用。
         * 2. 递归下个check 方法，n = 1，也就是第二列开始 算摆发。
         * 3. 在此期间，如果 列摆放不一样，就会回溯到 上一个操作中，重新上一个节点进行摆放。
         * 4. for 循环为 点睛之笔，不断的回溯，在 8 行中不停回溯，直到栈顶 top 进入else，退出第一次循环，此时 n ++ ,n = 1 ...
         * 5. 总结来说,并不是说 n = 0 就是第一次解法，个人的思想问题，导致迷糊了好久。
         */
        for (int i = 0; i < max; i++) {
            array[n] = i;
            // 点睛之笔 不冲突
            if (judge(n)) {

                /**
                 * 此回溯说明。
                 *  主要解释下，如何进行回溯
                 * 1. 假设 第一种解法已经ok, 说明 n == 8 的话 就是结束，那么回溯到当前调用栈。
                 * 2. array[7] = i +1  因为第一次解法已经完成。所以索引+1
                 * 3. 继续循环，得到合适列的摆放位置。
                 * 4. 如果当前列都不合适，就会返回到 array[6] = i +1 重复 1，2，3步骤，最终找到合适的。
                 */
                check(n + 1);
            }
        }

    }


    /**
     * 判断皇后是否在互相攻击
     * @param n
     * @return
     */
    private boolean judge(int n){
        for (int i = 0; i <n; i++) {

            // 判断是否在同一列，同一斜线下
            /**
             * 此判断说明
             * 1. array[i] = 0 ; array[n] = 0 在同一列
             * 2. Math.abs(0 - 0) = 0;
             * 3. Math.abs( 0 - 0) = 0
             *
             * 复杂点
             * 1. array[i] = 1 ; array[n] = 2 不在同一列
             * 2. Math.abs(2 - 1) = 1;
             * 3. Math.abs( 2 - 1) = 1             */
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])  ){
                return false;
            }

        }
        return true;

    }

    private void print(){
        count ++;
        for (int i : array) {
            System.out.printf("%d\t",array[i]);
        }
        System.out.println();
    }

}
